package Test;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import Utility.TreeNode;

import java.util.Map.Entry;
import java.util.PriorityQueue;

import SubjectListNode.MyLinkedList;

import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main m = new Main();
		
//		String[] a= {"cad","ab"};
//		char[] arts = a[0].toCharArray();
//		System.out.println(arts);
//		Arrays.sort(arts);
//		System.out.println(arts);
//		for(char art:arts) {
//			System.out.println(art);
//		}
		
//		Map<String,String> map = new HashMap<String,String>();
//		map.put("aa", "11");
//		map.put("bb", "22");
//		map.put("cc", "33");
//		map.put("aa", "12");
//		Set<Entry<String, String>> entrySet = map.entrySet();
//		for(Entry<String, String> o:entrySet) {
//			System.out.println(o.getKey()+","+o.getValue());
//		}
		
//		List<String> list1= new ArrayList<>();
//		list1.add("a");
//		list1.add("b");
//		list1.add("a");
//		list1.remove("a");
//		list1.remove("a");
//		list1.remove("a");
//		list1.remove("a");
//		System.out.println(list1);
		
		
//		long startTime = System.nanoTime();
//		int[][] a= {{1,2,3},{4,5,6},{7,8,9}};
//		int[][] b= m.Test3(a);
//		for(int i=0;i<b.length;i++) {
//			System.out.println("");
//			for(int j=0;j<b[i].length;j++) {
//				System.out.print(b[i][j]+",");
//			}
//		}
//		long endTime = System.nanoTime();
//		System.out.println(endTime-startTime);
		
		TreeNode treeNode = new TreeNode(0);
		
//		Map<String,String> map = new HashMap<>();
//		map.put("1", "a");
//		map.put("2", "b");
//		map.put("1", "c");
//		System.out.println(map);
//		int[] i= {2,1,3};
//		Arrays.sort(i);
//		int[] i2= {2,2,3,4,5};
//		for(int s:i) {
//			System.out.println(s);
//		}
		
//		String[] str1 = {"沉", "默", "王", "二","二"};
//		String[] str2 = {"沉", "默", "王", "二"};
//		String[] str3 = {"沉", "默", "2", "三","1"};
//		System.out.println(Arrays.mismatch(str1, str3));
		
//		Queue<String> q = new LinkedList<>();
//		q.add("aa");
//		q.offer("bb");
//		String s1 = q.peek();
////		String s2 = q.poll();
//		System.out.println(q +","+q.size());
//		System.out.println(null!="a");
		
//		List<Integer> l = new ArrayList<Integer>();
//		l.add(1);
//		l.add(2);
//		l.add(4);
//		l.add(3);
////		List<Integer> l2 = new ArrayList<Integer>();
////		l.add(2);
////		System.out.println(Collections.max(l));
//		l.stream().forEach(System.out::println);
		
//		MyLinkedList mll = new MyLinkedList();
//		mll.addAtHead(1);
//		mll.addAtTail(3);
//		mll.addAtIndex(1,2);
//		System.out.println(mll);
//		System.out.println(mll.get(1));
//		mll.deleteAtIndex(1);
//		System.out.println(mll);
//		System.out.println(mll.get(1));
//		mll.deleteAtIndex(1);
		
//		PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
//			@Override
//			public int compare(Integer n, Integer m) {
//				// TODO Auto-generated method stub
//				return m.compareTo(n);
//			}
//		});
//		queue.offer(1);
//		queue.offer(5);
//		queue.offer(3);
//		queue.offer(2);
//		queue.offer(4);
//		queue.offer(6);
//		
//		while(!queue.isEmpty()) {
//			System.out.print(queue.poll()+",");
//		}
		
		m.sort(new int[]{6,2,5,3,1,4}, 0, 5);
		
		
		List<Integer> l = new ArrayList<>();
		l.add(5);
		l.add(3);
		l.add(1);
		l.add(2);
		l.add(4);
		System.out.println(l);
		l.sort(new Comparator<Integer>() {

			@Override
			public int compare(Integer arg0, Integer arg1) {
				// TODO Auto-generated method stub
				return arg0<arg1?-1:0;
			}
			
		});
		System.out.println(l);
	}
	
	//快排
	public void sort(int[] array, int left, int right) {
		if(left>right) {
			return;
		}
		int base = array[left];
		int i=left,j=right;
		while(i!=j) {
			while(array[j]>=base&&i<j) {
				j--;
			}
			while(array[i]<=base&&i<j) {
				i++;
			}
			if(i<j) {
				int temp = array[i];
				array[i]=array[j];
				array[j]=temp;
			}
		}
		array[left]=array[i];
		array[i]=base;
		
		sort(array,left,i-1);
		sort(array,i+1,right);
	}
}
